package com.fang.algorithm.zuo.linked;

/**
 * @author lingxiao.fang
 * @Desc 双向链表模拟栈和队列
 * @createTime 2025/2/9 17:07
 */
public class Test05_DoubleLinkedListMockStackAndQueue {

    /**
     * 双向链表
     */
    public static class Test05Node<T> {
        private T value;
        private Test05Node<T> last;
        private Test05Node<T> next;

        public Test05Node(T value) {
            this.value = value;
        }
    }

    /**
     * 双向链表模拟队列
     */
    public static class Test05Queue<T> {
        private T value;
        private Test05Node<T> head;
        private Test05Node<T> tail;

        public void addToHead(T value) {
            Test05Node<T> curr = new Test05Node<>(value);
            if (head == null) {
                head = curr;
                tail = curr;
            } else {
                curr.next = head;
                head.last = curr;
                head = curr;
            }
        }

        public void addToTail(T value) {
            Test05Node<T> curr = new Test05Node<>(value);
            if (tail == null) {
                head = curr;
                tail = curr;
            } else {
                curr.last = tail;
                tail.next = curr;
                tail = curr;
            }
        }

        public T popToHead() {
            if (head == null) {
                return null;
            }
            if (head == tail) {
                T value = head.value;
                head = null;
                tail = null;
                return value;
            } else {
                T value = head.value;
                head = head.next;
                head.last = null;
                return value;
            }
        }

        public T popToTail() {
            if (tail == null) {
                return null;
            }
            if (tail == head) {
                T value = tail.value;
                head = null;
                tail = null;
                return value;
            } else {
                T value = tail.value;
                tail = tail.last;
                tail.next = null;
                return value;
            }
        }
    }

    public static class Test05MockQueue<T> {
        private final Test05Queue<T> queue = new Test05Queue<>();

        public void offer(T value) {
            queue.addToTail(value);
        }

        public T pop() {
            return queue.popToHead();
        }
    }

    public static class Test05MockStack<T> {
        private final Test05Queue<T> queue = new Test05Queue<>();

        public void push(T value) {
            queue.addToHead(value);
        }

        public T pop() {
            return queue.popToHead();
        }
    }

    public static void main(String[] args) {
        Test05MockQueue<Integer> queue = new Test05MockQueue<>();
        for (int i = 0; i < 5; i++) {
            queue.offer(i);
        }
        for (int i = 0; i < 6; i++) {
            Integer value = queue.pop();
            System.out.println(value);
        }
        System.out.println("========");
        Test05MockStack<Integer> stack = new Test05MockStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
        }
        for (int i = 0; i < 4; i++) {
            Integer value = stack.pop();
            System.out.println(value);
        }
    }
}
